package com.datastructure.test.insertinterval;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class InsertInterval {

    public static void main(String[] args) {

    }

    public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) {
        // write code here
        ArrayList<Interval> res = new ArrayList<>();
        ArrayList<Interval> data = new ArrayList<>();
        Collections.addAll(res, Intervals);
        res.add(newInterval);
        List<Interval> collect = res.stream().sorted(Comparator.comparingInt(interval -> interval.start)).collect(Collectors.toList());
        int index = -1;
        for (Interval interval : collect) {
            if(index==-1||data.get(index).end< interval.start){
                data.add(interval);
                index++;
            } else {
                data.get(index).end=Math.max(interval.end,data.get(index).end);
            }
        }
        Interval[] result = new Interval[data.size()];
        for (int i = 0; i < data.size(); i++) {
            result[i]= data.get(i);
        }
        return result;
    }

}

class Interval {
   int start;
   int end;
   public Interval(int start, int end) {
     this.start = start;
     this.end = end;
   }
 }
